#include "BST.h"
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <stdint.h>
#include "LinkedQueue.h"
/*
    Insert_Node:往一棵二叉排序树上增加节点，增加之后继续保持其排序性
*/
struct BitNode*Insert_Node(struct BitNode*root,TElemType d)
{
    //创建一个新节点并赋值
    struct BitNode*pnew = malloc(sizeof(*pnew));
    if(pnew == NULL)
        return root;
    pnew->data = d;
    pnew->lchild = pnew->rchild = NULL;

    if(root == NULL)
        return pnew;
    //查找
    struct BitNode*p = root;
    struct BitNode*pf = NULL;// 指向p的父节点
    while(p)
    {
        if(p->data > pnew->data)
        {
            pf = p;
            p = p->lchild;
        }
        else if(p->data < pnew->data)
        {
            pf = p;
            p = p->rchild;
        }
        else
        {
            free(pnew);
            return root;
        }
    }

    //增加
    if(pf->data > pnew->data)
    {
        pf->lchild = pnew;
    }
    else
    {
        pf->rchild = pnew;
    }

    return root;
}
/*
    Create_input_BitSortTree:从键盘上输入数据创建一棵二叉排序树

    参数：无

    返回值：
        返回根节点指针
*/
struct BitNode*Create_input_BitSortTree()
{
    struct BitNode*root = NULL;//空树
    while(1)
    {
        TElemType ch;
        scanf("%d", &ch);
        if(ch == 0)
            break;
        
        root = Insert_node_1(root, ch);
    }

    return root;
}

//先序遍历
void Pre_order(struct BitNode*root)
{
    if(root == NULL)
        return;
    //先根
    printf("%d ", root->data);
    //左子树
    Pre_order(root->lchild);

    //右子树
    Pre_order(root->rchild);

}
//中序遍历
void Mid_order(struct BitNode*root)
{
    if(root == NULL)
        return;
    
    //左子树
    Mid_order(root->lchild);

    //中根
    printf("%d ", root->data);

    //右子树
    Mid_order(root->rchild);

}
//后序遍历
void Post_order(struct BitNode*root)
{
    if(root == NULL)
        return;
    
    //左子树
    Post_order(root->lchild);

    //右子树
    Post_order(root->rchild);

    //后根
    printf("%d ", root->data);

    

}
/*
	Delete_Node:在一棵二叉排序树上删除一个值为d的节点，删除之后依然保持下二叉排序性
	
	参数：
		@root:
		@d:
	返回值：
		根节点返回
*/
struct BitNode*Delete_Node(struct BitNode*root,TElemType d)
{
    //查找
    struct BitNode*p = root;//遍历指针
    struct BitNode*pf = NULL;//指向p的父节点
    while(p)
    {
        if(p->data > d)
        {
            pf = p;
            p = p->lchild;
        }
        else if(p->data < d)
        {
            pf = p;
            p = p->rchild;
        }
        else
        {
            break;
        }
    }
    if(p == NULL)
    {
        return root;
    }
    //删除
Delete:
    if(p->lchild == NULL && p->rchild == NULL)//无孩子
    {
        //有无父节点
        if(pf == NULL)// 删除的就是根节点，且这棵树只有一个节点
        {
            free(p);
            root = p = NULL;
            return NULL;
        }
        else if(pf->lchild == p)
        {
            pf->lchild = NULL;
            free(p);
            p = NULL;
        }
        else if(pf->rchild == p)
        {
            pf->rchild = NULL;
            free(p);
            p = NULL;
        }
    }
    else if(p->lchild != NULL && p->rchild == NULL)//有左子节点
    {
        //有无父节点
        if(pf == NULL)// 删除的就是根节点
        {
            root = p->lchild;
            p->lchild = NULL;
            free(p);
            p = NULL;
        }
        else if(pf->lchild == p)
        {
            pf->lchild = p->lchild;
            p->lchild = NULL;
            free(p);
            p = NULL;
        }
        else if(pf->rchild == p)
        {
            pf->rchild = p->lchild;
            p->lchild = NULL;
            free(p);
            p = NULL;
        }
    }
    else if(p->lchild == NULL && p->rchild != NULL)//有右子节点
    {
        //有无父节点
        if(pf == NULL)// 删除的就是根节点
        {
            root = p->rchild;
            p->rchild = NULL;
            free(p);
            p = NULL;
        }
        else if(pf->lchild == p)
        {
            pf->lchild = p->rchild;
            p->rchild = NULL;
            free(p);
            p = NULL;
        }
        else if(pf->rchild == p)
        {
            pf->rchild = p->rchild;
            p->rchild = NULL;
            free(p);
            p = NULL;
        }
    }
    else// 有两个孩子节点
    {
        //删除的是有两个孩子节点的节点：左子树找最大或右子树中找最小 来进行替操作
        struct BitNode*pk = p->lchild;// pk去左子树中找最大
        while(pk->rchild)
        {
            pf = pk;
            pk = pk->rchild;
        }// pk 此时所在位置就是要替换的位置

        p->data = pk->data;
        p = pk;

        //pk 此时是要删除的节点
        goto Delete;
    }

    return root;
}
bool Judge_l(TElemType r_d, struct  BitNode*root)
{
    if(root == NULL)
        return true;
    //创建队列
    struct LinkedQueue*q = InitQueue();
    if(q == NULL)
        return false;
    
    //根节点入队
    EnQueue(q,  root);

    while(!QueueIsEmpty(q))
    {
        //出队
        QElemType d;
        DeQueue(q, &d);
        if(r_d <= d->data)
        {
            DestroyQueue(q);
            return false;
        }
                   
        //出队元素的孩子节点入队
        if(d->lchild)
            EnQueue(q, d->lchild);
        if(d->rchild)
            EnQueue(q, d->rchild);
    }
    
    //销毁队列
    DestroyQueue(q);

    return true;

    
}
bool Judge_r(TElemType r_d, struct  BitNode*root)
{
    if(root == NULL)
        return true;
    //创建队列
    struct LinkedQueue*q = InitQueue();
    if(q == NULL)
        return false;
    
    //根节点入队
    EnQueue(q,  root);

    while(!QueueIsEmpty(q))
    {
        //出队
        QElemType d;
        DeQueue(q, &d);
        if(r_d >= d->data)
        {
            DestroyQueue(q);
            return false;
        }
                   
        //出队元素的孩子节点入队
        if(d->lchild)
            EnQueue(q, d->lchild);
        if(d->rchild)
            EnQueue(q, d->rchild);
    }
    
    //销毁队列
    DestroyQueue(q);

    return true;

    
}
/*
    Is_sortBitTree：判断是否为一棵二叉排序树
*/
bool  Is_sortBitTree(struct BitNode*root)
{
    if(root == NULL)
        return true;
    if(root->lchild == NULL && root->rchild == NULL)
    {
        return true;
    }
        
    if(!Judge_l(root->data, root->lchild))
        return false;
    if(!Judge_r(root->data,root->rchild))
        return false;

    if(!Is_sortBitTree(root->lchild))	
        return false;

    if(!Is_sortBitTree(root->rchild))	
        return false;
    return true;
}
/*
    Level_Travel:对一棵二叉排序树进行层次遍历
    @root :根节点
*/
void Level_Travel(struct BitNode*root)
{
    printf("Level_Travel:");
    if(root == NULL)
    {
        printf("\n");
        return ;
    }
       
    //创建队列
    struct LinkedQueue*q = InitQueue();
    if(q == NULL)
        return;
    
    //根节点入队
    EnQueue(q,  root);

    while(!QueueIsEmpty(q))
    {
        //出队
        QElemType d;
        DeQueue(q, &d);
        printf("%d ", d->data);
        
        //出队元素的孩子节点入队
        if(d->lchild)
            EnQueue(q, d->lchild);
        if(d->rchild)
            EnQueue(q, d->rchild);
    }
    
    //销毁队列
    DestroyQueue(q);

    printf("\n");
}
/*
	Get_H:求一棵二叉排序树的深度
*/
int Get_H(struct BitNode*root)
{
    if(root == NULL)
        return 0;
    int l = Get_H(root->lchild);
    int r = Get_H(root->rchild);
    return l>r ? l+1 : r+1;
}
/*
	Insert_node_1:往一棵二叉排序树上增加节点，并保持其排序性
	@root :根节点
	@val :要增加的节点的值
	
	返回值：
		返回树的根节点
*/
struct BitNode*Insert_node_1(struct BitNode*root, TElemType d)
{
    //创建一个新节点并赋值
    struct BitNode*pnew = malloc(sizeof(*pnew));
    if(pnew == NULL)
        return root;
    pnew->data = d;
    pnew->lchild = pnew->rchild = NULL;

    if(root == NULL)
        return pnew;
    else if(d > root->data)
    {
        root->rchild = Insert_node_1(root->rchild, d);
        //free(pnew);
    }
    else if(d < root->data)
    {
        root->lchild = Insert_node_1(root->lchild, d);
        //free(pnew);
    }
    //
    free(pnew);
    return root;
}

/*
    Is_sortBitTree_1：判断是否为一棵二叉排序树
*/
bool  Is_sortBitTree_1(struct BitNode*root, int n,TElemType* d)
{
    if(root == NULL)
        return true;
    if(root->lchild == NULL && root->rchild == NULL)
    {
        *d = root->data;
        return true;
    }
    if(root->lchild && root->lchild->data >= root->data)
        return false;
    if(root->rchild && root->rchild->data <= root->data)
        return false;    
    int max = INT32_MIN;//左子树中求最大
    if(!Is_sortBitTree_1(root->lchild, 0,&max) )
        return false;
    int min = INT32_MAX;//右子树中求最小
    if(!Is_sortBitTree_1(root->rchild, 1, &min) )
        return false;    
    
    if(max < root->data && min > root->data)
    {
        if(max == INT32_MIN)
            *d = min;
        else if(min == INT32_MAX)
            *d = max;
        else if(n)
            *d = max;
        else 
            *d = min;
       
        return true;
    }
    return false; 
}